package com.zhugang.week13.dp;

/**
 * @program algorithms
 * @description: BagesByDP
 * @author: chanzhugang
 * @create: 2022/09/14 23:27
 */
public class BagesByDP {

    /**
     * 0-1背包问题：可装最大重量？
     * dp解法
     *
     * @param weight
     * @param n
     * @param w
     * @return
     */
    public int knapsack(int[] weight, int n, int w) {
        // dp[i][j]：第i个物品装入背包重量为j ，是否可达
        boolean[][] dp = new boolean[n][w + 1];
        dp[0][0] = true;
        if (weight[0] <= w) {
            dp[0][weight[0]] = true;
        }

       /* for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j]) {
                    // 不装
                    dp[i][j] = true;
                }
                if (j + weight[i] <= w) {
                    // 装
                    dp[i][j + weight[i]] = true;
                }
            }
        }*/
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] || (j - weight[i] >= 0 && dp[i - 1][j - weight[i]])) {
                    // 状态转移方程： dp[i][j] = dp[i - 1][j] || dp[i - 1][j - weight[i]]
                    dp[i][j] = true;
                }
            }
        }
        // 最后一行找最大值 （逆序）
        for (int i = w; i >= 0; i--) {
            if (dp[n - 1][i]) {
                return i;
            }
        }
        return 0;
    }
}